package com.cdream.basic.algorithm.leetcode.tree;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author cdream
 * @date 7/31/21
 */
public class Question987 {
    Map<Integer, List<int[]>> res = new TreeMap<>();

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        addToMap(root, 0, 0);
        List<List<Integer>> r = new ArrayList<>();
        Comparator<int[]> c = Comparator.comparingInt(a -> a[1]);
        res.values().forEach(a-> {
            List<Integer> i =
                    a.stream().sorted(c.thenComparingInt(b->b[0])).map(b -> b[0]).collect(Collectors.toList());
            r.add(i);
        });
        return r;
    }

    public void addToMap(TreeNode node, Integer col, Integer row) {
        if (node == null) {
            return;
        }
        List<int[]> list = res.getOrDefault(col, new ArrayList<int[]>());
        list.add(new int[]{node.val, row});
        res.put(col, list);
        addToMap(node.left, col - 1, row + 1);
        addToMap(node.right, col + 1, row + 1);

    }

}
